#include<vector>
#include<algorithm>
#include<time.h>
using namespace std;
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        srand(time(NULL));
        quicksort(0,nums.size()-1,nums);
        return nums;
    }
    //数组分三块快排
    void quicksort(int left,int right ,vector<int>& nums){
        if(left >= right) return;
        int key = getkey(left,right,nums);
        int i = left,l = left-1 ,r = right+1;
        while(i<r){
            if(nums[i] < key)   swap(nums[++l],nums[i++]);
            else if(nums[i] == key) ++i;
            else if(nums[i] > key)  swap(nums[--r],nums[i]);
        }
        //[left,l]   [r,right]
        quicksort(left,l,nums);
        quicksort(r,right,nums);

    }
    int getkey(int left,int right,vector<int>& nums){
        int r = rand()%(right-left+1) + left;
        return nums[r];
    }
};

int main(){
    vector<int> v{5,1,1,2,0,0};
    Solution().sortArray(v);
    return 0;
}